The present invention relates to method and apparatus for generating parity characters for a codeword of a cyclic code.
An error correction code (ECC) is widely employed to detect or to correct errors in data. In general, parity characters of an ECC are calculated based on message characters to be transmitted and appended after the message characters to form a codeword. When a receiver receives the codeword, it may be able to correct a transmission error within the received message characters according to the parity characters of the codeword. A cyclic code is a kind of ECC and is commonly used in different fields. For example, the Reed-Solomon (RS) code employed in optical storage systems is a cyclic code.
Please refer to FIG. 1, which depicts a schematic diagram of a conventional codeword 100 of a cyclic code. The codeword 100 is composed of a data block (i.e. message block) 110 and a parity section 120. The format of the codeword 100 is similar to most cyclic codewords. Generally, the data block 110 can be regarded as a message polynomial M(x), and the parity section 120 can be regarded as a parity polynomial P(x). When encoding the message characters into the codeword 100, a serial encoder is typically employed to divide the message polynomial M(x) by a generator polynomial g(x) in order to compute the parity polynomial P(x), which is the remainder of the division.
In practical implementations, however, the parity characters of some cyclic codes are not located in the end of the codeword. For example, the well-known CIRC (cross-interleaved Reed-Solomon code) employed in the CD specification adopts a (28, 24) shortened Reed-Solomon code as an outer code. A codeword composed of twenty eight characters is encoded with the shortened RS(28, 24) code over a finite field GF(28) by calculating four parity characters based on twenty four message characters. As shown in FIG. 2, in the CD specification, the four parity characters are located in the middle of the codeword instead of the end of the codeword.
FIG. 2 is a schematic diagram of a codeword 200 encoded with the shortened RS(28, 24) code over GF(28). The codeword 200 is employed in the CD specification. The codeword 200 is composed of a first data block 210, a second data block 230 and a parity section 220. The first data block 210 and the second data block 230 are each a part of the message characters to be transmitted. A difference between the codeword 200 and the codeword 100 is that the parity section 220 of the codeword 200 is located in the middle of the codeword instead of the end of the codeword 200. In the following, the first data block 210 to the left of the parity section 220 is designated as a polynomial L(x), the second data block 230 to the right of the parity section 220 is designated as a polynomial R(x), and the parity section 220 is designated as a parity polynomial P(x). In other words, the codeword 200 encoded with the shortened RS(28, 24) code over GF(28) can be represented as a codeword polynomial C(x)=L(x)x16+P(x)x12+R(x).
Since the shortened RS(28, 24) code employed in the CD specification requires that the parity characters be located in intermediate symbol locations in the codeword 200, it is not possible to encode the message characters in serial fashion using a serial encoder in accordance with shortened RS(28, 24) code. But the codeword 200 could be cyclically shifted to form another valid codeword due to the nature of the cyclic code, i.e., any shift of a codeword of a cyclic code is another codeword. Therefore, the conventional art cyclically shifts all message characters of the second data block 230, which is to the right of the parity section 220, to the left-most symbol locations, so that the parity characters are located at the end of the shifted codeword.
FIG. 3 illustrates a schematic diagram of a codeword 300, which is a shifted version of the codeword 200 of FIG. 2. As mentioned above, since the codeword 200 is a codeword of a cyclic code, the shifted codeword 300 is a valid codeword. As shown in FIG. 3, the second data block 230, which is at the right end of the codeword 200, now appear at the left end of the codeword 300 and the parity section 220 becomes the right-most portion of the codeword 300. However, as is well known in the art, a zero-value section 310, which is composed of a long string of zero-value characters, is inserted between the first data block 210 and the second data block 230 of the shifted codeword 300. In the case of the CIRC employed in the CD specification, the length of the string of zeros in the zero-value section 310 would be 227. Accordingly, the codeword 300 can be represented as a codeword polynomial CCIRC(x)=R(x)x243+L(x)x4+P(x). As a result, the parity characters (i.e., the coefficients of the polynomial P(x)) can be computed through the serial encoder. However, it requires 251 computing cycles to compute the parity characters.
In order to improve the computational speed in computing the parity characters, E. J. Weldon et al. disclose a high speed encoder in U.S. Pat. No. 5,140,596. In this patent, the required computing cycles are reduced to 12 in computing the parity characters of the CIRC. However, the encoding method disclosed by Weldon et al. cannot meet the need for higher encoding speed.